package com.nl.sort;

import java.util.Arrays;

/**
 * 
 * @author supertool
 *
 */
public class QuickSort {

	private QuickSort() {
	}

	public static <T extends Comparable<T>> void sort(T[]arr,int left,int right){
		if(left<right&&right<=arr.length-1){
			int index = partition(arr,left,right);
			sort(arr,left,index-1);
			sort(arr,index+1,right);
		}

	}

	private static <T extends Comparable<T>> int partition(T[]arr,int start,int end){
		if(arr!=null&&start<end&&end<arr.length){
			int l=start,r=end;
			T  p= arr[start];
			while(l<r){
				while(l<r&&arr[r].compareTo(p)<=0){
					r--;
				}
				while(l<r&&arr[l].compareTo(p)>0){
					l++;
				}
				if(l<r){
					swap(arr,l,r);
				}
			}
			swap(arr,start,l);
			return l;
		}else{
			throw new RuntimeException();
		}
	}

	private static <T> void swap(T[]arr,int i,int j){
		T tmp = arr[i];
		arr[i] = arr[j];
		arr[j] =tmp;
	}
	public static void main(String[] args) {
		Integer[] arr = new Integer[]{12,32,3,4,43,44,100};
		sort(arr, 0, arr.length-1);
		System.out.println(Arrays.toString(arr));
	}
}

